package code;

import java.util.Arrays;

public class 剑指offer10_II {
    int[] dp=new int[3];
    final int MAX=(int)1e9+7;
    public int numWays_1(int n) {
        /***
         * 1、和剑指offer10-I很像，用了循环数组的技巧，我总结了一下思路在有道云算法笔记中
         */
        dp[0]=dp[1]=1;
        for(int i=2;i<=n;++i)dp[i%3]=(dp[(i-1)%3]%MAX+dp[(i-2)%3]%MAX)%MAX;
        return dp[n%3];
    }
    final int MOD=(int) 1e9+7;
    class Matrix{
        long[][] data;
        int row,col;
        Matrix(int m,int n){
            // data=new int[m][n];
            row=m;col=n;
        }

        public void setData(long [][] data) {
            this.data = data;
        }
    }
    class MatrixTools{
        Matrix  mutiple(Matrix m1,Matrix m2){
            long [][] res=new long  [m1.row][m2.col];
            for(int i=0;i<m1.row;++i)
                for(int j=0;j<m2.col;++j)
                    for(int k=0;k<m1.col;++k)
                        res[i][j]=(res[i][j]+m1.data[i][k]*m2.data[k][j])%MOD;
            Matrix m3=new Matrix(m1.row,m2.col);
            m3.setData(res);
            return m3;
        }
    }
    public int numWays(int n) {
        /***
         * 2、快速矩阵幂,(fn-1,fn)=(f0,f1)B^n=A*B^n
         */
        Matrix B = new Matrix(2, 2);
        MatrixTools matrixTools = new MatrixTools();
        B.setData(new long[][]{{0,1},{1,1}});
        Matrix A0=new Matrix(1,2);
        A0.setData(new long[][]{{1,1}});
        Matrix res=new Matrix(2,2);
        res.setData(new long[][]{{1,0},{0,1}});
        for(;n>0;n>>=1,B=matrixTools.mutiple(B,B))if((n&1)>0){res=matrixTools.mutiple(res,B);}
        res=matrixTools.mutiple(A0,res);
        return (int)res.data[0][0];
    }
}
